package LeetCode;

import org.omg.PortableInterceptor.INACTIVE;

import javax.print.AttributeException;
import java.util.Scanner;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}17:03
 */
public class LeetCode866 {
    public int primePalindrome(int N) {
        while (true) {
            N = getNextPalindrome(N); // 获取>=N的回文数
            if(isPrime(N)) return N; // 判断是不是素数
            N++;
        }
    }

    // 获取下一个>=n的回文数
    private int getNextPalindrome(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int mid = s.length/2;
        while (true) {
            // 制造回文数：把前半段翻转一下复制到后半段
            for (int i = 0; i < mid; i++) {
                s[s.length -1 - i] = s[i];
            }
            // 判断制造出来的数是否>=n
            int tmp = Integer.valueOf(String.valueOf(s));
            if (tmp >= n) return tmp; // 如果>=n，返回这个造出来的数
                // 如果比n小，那前半段+1
            else {
                int j = s.length % 2 == 1? mid: mid-1; // 如果是奇数长度，最靠近中轴的是s[mid]；如果是偶数长度，最靠近中轴的是s[mid-1]
                // 有9要进位（不用考虑999xxx这样首位要进位的，因为999999这个回文数肯定>=所有999xxx形式的n）
                while (s[j] == '9'){
                    s[j--] = '0';
                }
                s[j]++;
            }
        }
    }

    // 判断是否是素数
    private boolean isPrime(int num){
        // 一般从2找到n/2，判断是否能被整除。从5开始，n/2>√n，这样可以减少运算量。
        if(num <= 5) {
            return num == 2 || num == 3 || num == 5;
        }

        // 从2找到√num
        int index = (int) Math.sqrt(num);
        for (int i = 2; i <= index; i++){
            if (num % i == 0){
                System.out.println(i);
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode866().primePalindrome(10000));
    }
}


